CS126                                     March 9, 1970

                       NOTES ON LISP NOTATION

1.S-expressions
	1.1 Atoms A, A3, PLUS, etc.
	1.2 Compound S-expressions  (A.B), (A.(B.C)), etc.
	1.3 List notation  (A B C), ((A B) A C), etc.

2. Basic operators - car[x], cdr[x], cons[x,y], atom[x], eq[x,y]
	Examples car[((A.B).C)] = (A.B)
		cdr[((A.B).C)] = C
		cons[(A.B) , C] = ((A.B).C)
		atom[A] = T, atom[(A.B)] = F
		eq[A,B] = F, eq[A,(A.B)] = F, eq[(A.B),(A.C)] = F
		eq[A,A] = T, eq[(A.B),(A.B)] has value  T  if the
two copies of (A.B) are represented by the same pointer in memory.

3.In list notation we have
		car[(A B C D)] = A
		cdr[(A B C D)] = (B C D)
		cons[A,(B C D)] = (A B C D)
All this is a consequence of the fact that (A B C D) can be regarded
as merely an abbreviation for  (A.(B.(C.(D.NIL)))).

4. Abbreviations
	ax  for  car[x]  so that  a(A B C) = A
	dx  for  cdr[x]  so that  d(A B C) = (B C)
	x.y  for  cons[x,y]  so that  A.(B C D) = (A B C D) {Although
this notation is convenient it tempts the inexperienced to confuse
the cons operation with the  .  of the dot notation.}
	adaax  for  car[cdr[car[car[x]]]], etc. which can also
be written  cadaar[x]  constituting a lesser abbreviation.
	nx  for  eq[x,NIL], {also written  null[x]}.
	(x y ... z)  for  cons[x,cons[y,...cons[z,NIL]...]] {This
is the operation that forms lists from the elements.  It is also
denoted by  list[x,y,...,z].  The ... is intended to indicate
that the operation can take an arbitrary number of arguments.}
	atx  for  atom[x]
	x eq y  for eq[x,y]
	x=y  for  equal[x,y]
	x∧y  for  if x then y else F
	x∨y  for  if x then T else y
	¬x  for  if x then F else T

5. Examples of simple LISP programs.
	5.1 Alternate elements of a list.
alt[x] = if nx ∨ ndx then x else [ax].alt[ddx]
Thus  alt[(A B C D E)] = (A C E)
	5.2 Substitution of  x  for  y  in  z.
subst[x,y,z] = if atz then [if z eq y then x else z]
	else subst[x,y,az].subst[x,y,dz]
Thus  subst[(TIMES X Y),X,(PLUS X Y)] = (PLUS (TIMES X Y) Y)
	5.3 Membership of an atom in a list of atoms.
member[x,u] = ¬nu∧[x eq au ∨ member[x,du]]
Thus  member[A,(A B C)] =T  and  member[A,(B C D)] = F.
	5.4 Inclusion of one list in another.
included[u,v] = nu ∨ [member[au,v] ∧ included[du,v]]
Thus  included[(A B C),(D C B A)] = T.
	5.5 The union of two lists.
union[u,v] = if nu then v else if member[au,v] then union[du,v]
else [au].union[du,v]